import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-08-31
 * Time: 9:13
 */
/*
 *如和理解递归问题
 * 1.重复子问题
 * 大问题——》相同类型的子问题
 * 相同类型子问题——》相同类型问题
 * 2.如和编写递归代码
 * 函数头void dfs(list a.list b,list c,int n)
 * 将a上的盘子借助b移动到c上
 * 函数体
 * 将a上的n个盘子借助b移动到c上
 * dfs(list a.list b,list c,int n-1)
 * 将a上的最后一个盘子已到c上
 * 将b上的n个盘子借助a移动到c上
 * dfs(list b.list a,list c,int n-1)
 * 3.递归函数出口
 * n==1
 * 出口
 * */
public class test_1 {
    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
    }

    private static void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int size) {
        if (size == 1) {
            c.add(a.remove(a.size() - 1));
            return;
        }
        dfs(a, c, b, size - 1);
        c.add(a.remove(a.size() - 1));
        dfs(b, a, c, size - 1);
    }

}
